package com.hfb.mashibing.alip8.diamondsquarealgorithm.class10;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Map.Entry;

/**
 * 最短路径算法-迪杰斯特拉(Dijkstra)算法
 * 迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。
 * 它的主要特点是以起始点为中心向外层层扩展(广度优先遍历思想)，直到扩展到终点为止。
 *
 *
 * 基本思想
 *
 * 通过Dijkstra计算图G中的最短路径时，需要指定一个起点D(即从顶点D开始计算)。
 * 此外，引进两个数组S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，
 * 而U则是记录还未求出最短路径的顶点(以及该顶点到起点D的距离)。
 * 初始时，数组S中只有起点D；数组U中是除起点D之外的顶点，并且数组U中记录各顶点到起点D的距离。
 * 如果顶点与起点D不相邻，距离为无穷大。然后，从数组U中找出路径最短的顶点K，并将其加入到数组S中；
 * 同时，从数组U中移除顶点K。接着，更新数组U中的各顶点到起点D的距离。
 * 重复第4步操作，直到遍历完所有顶点。
 *
 *Dijkstra算法过程：
 * 1)Dijkstra算法必须指定一个源点
 * 2)生成一个源点到各个点的最小距离表，一开始只有一条记录，即原点到自
 * 己的最小距离为0，源点到其他所有点的最小距离都为正无穷大
 * 3)从距离表中拿出没拿过记录里的最小记录，通过这个点发出的边，更新源
 * 点到各个点的最小距离表，不断重复这一步
 * 4)源点到所有的点记录如果都被拿过一遍，过程停止，最小距离表得到了
 *
 */

// no negative weight 没有负权重
public class Code06_Dijkstra {


    public static Map<Node, Integer> dijkstra1(Node head) {
        // 从haed出发到所有点的最小距离
        // key:从head出发到达key
        // value:从head出发到达key的最小距离
        // 如果在表中没有T的记录，含义是从head出发到T这个点的距离为正无穷
        Map<Node, Integer> distanceMap = new HashMap<>();
        distanceMap.put(head, 0);
        // 已经求过距离的节点，存在selectedNodes中，以后再也不碰
        HashSet<Node> selecteNodes = new HashSet<>();
        Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selecteNodes);
        // form 0
        while (minNode != null) {
            int distance = distanceMap.get(minNode);
            minNode.edges.forEach(edge->{
                Node toNode = edge.to;
                if (!distanceMap.containsKey(toNode)){
                    distanceMap.put(toNode, distance+edge.weight);
                } else {
                    distanceMap.put(toNode,
                                    Math.min(distanceMap.get(toNode), distance+edge.weight));
                }
            });
            selecteNodes.add(minNode);
            minNode = getMinDistanceAndUnselectedNode(distanceMap, selecteNodes);
        }
        return distanceMap;
    }

    private static Node getMinDistanceAndUnselectedNode(Map<Node, Integer> distanceMap,
                                                        HashSet<Node> touchedNodes) {
        Node minNode = null;
        int minDistance = Integer.MAX_VALUE;
        for (Entry<Node, Integer> set:distanceMap.entrySet()){
            Node node = set.getKey();
            int distance = set.getValue();
            if(!touchedNodes.contains(node) && distance<minDistance){
                minNode = node;
                minDistance = distance;
            }
        }
        return minNode;
    }
    public static class NodeRecord{
        public Node node;
        public int distance;

        public NodeRecord(Node node, int distance) {
            this.node = node;
            this.distance = distance;
        }
    }

    /** 小根堆
     *
     */
    public static class NodeHead{
        public Node[] nodes;// 实际堆结构
        // 堆的位置表：key 某一个node，value 上面数组中的位置
        private HashMap<Node,Integer> heapIndexMap;
        // 堆的距离表： key 某一个节点，value 从源节点出发到改节点的目前最小距离
        private HashMap<Node,Integer> distanceMap;
        public int size;// 堆上节点的个数

        public NodeHead(int size) {
            this.nodes = new Node[size];
            this.heapIndexMap = new HashMap<>();
            this.distanceMap = new HashMap<>();
            this.size = 0;
        }
        public boolean isEmpty(){
            return size == 0;
        }

        /**
         * 有一个node点，现在发现了一个从源节点出发到达node的距离为distance
         * 判断要不要更新，若需要就更新
         * @param node
         * @param distance
         */
        public void addOrUpdateOrIgnore(Node node, int distance){
            if (inHeap(node)) {// 在堆上
                distanceMap.put(node, Math.min(distanceMap.get(node), distance));
                insertHeapify(node, heapIndexMap.get(node));
            }
            if (!isEntered(node)) {// 没进来过
                nodes[size] = node;
                heapIndexMap.put(node, size);
                distanceMap.put(node, distance);
                insertHeapify(node, size++);
            }
        }
        // 弹出/出堆
        public NodeRecord pop(){
            NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0]));
            swap(0, size-1);
            heapIndexMap.put(nodes[size-1], -1);
            distanceMap.remove(nodes[size-1]);
            // free
            nodes[size-1] = null;
            heapify(0, --size);
            return nodeRecord;
        }
        private void insertHeapify(Node node, int index){
            while (distanceMap.get(nodes[index]) < distanceMap.get(node)){
                swap(index, (index-1)/2);
                index = (index-1)/2;
            }
        }
        private void heapify(int index, int size){
            int left = index * 2 + 1;
            while (left < size){
                int smalllest = left+1<size && distanceMap.get(nodes[left+1])<distanceMap.get(nodes[left])
                                ? left+1
                                : left;
                smalllest = distanceMap.get(nodes[smalllest]) < distanceMap.get(nodes[index])
                            ? smalllest
                            : index;
                if (smalllest == left) break;
                swap(smalllest, index);
                index = smalllest;
                left = index*2+1;
            }
        }
        // 节点Node是否进来过？
        private boolean isEntered(Node node){
            return heapIndexMap.containsKey(node);
        }
        // 节点Node是否在堆上？
        private boolean inHeap(Node node){
            return isEntered(node) && heapIndexMap.get(node)!=-1;
        }
        private void swap(int index1, int index2){
            heapIndexMap.put(nodes[index1], index2);
            heapIndexMap.put(nodes[index2], index1);
            Node tmp = nodes[index1];
            nodes[index1] = nodes[index2];
            nodes[index2] = tmp;
        }
    }

    /**
     *  改进后的dijkstra算法：
     *      从head 出发,所有head能到达的点，
     *      生成到达每个节点的最小路径记录并返回
     * @param head
     * @param size
     * @return
     */
    public static HashMap<Node, Integer> dijkstra2(Node head,int size){
        NodeHead nodeHead = new NodeHead(size);// 堆
        nodeHead.addOrUpdateOrIgnore(head, 0);
        HashMap<Node, Integer> result = new HashMap<>();
        while (!nodeHead.isEmpty()){
            NodeRecord record = nodeHead.pop();
            Node cur = record.node;
            int distance = record.distance;
            for (Edge edge : cur.edges) {
                nodeHead.addOrUpdateOrIgnore(edge.to, edge.weight+distance);
            }
            result.put(cur,distance);
        }
        return result;
    }
//00856 13716304347
}
